package com.parsechina.hpush.broker;

import java.util.Deque;
import java.util.LinkedList;
import java.util.Random;

/**
 * @author linfeng
 * @since 2016/12/6
 */
public class Trie {

    static class Node {
        char content; // the character in the node
        boolean isEnd; // whether the end of the words
        int count;  // the number of words sharing this character
        Deque<Node> childList; // the child list

        public Node(char c) {
            childList = new LinkedList<Node>();
            isEnd = false;
            content = c;
            count = 0;
        }

        public Node subNode(char c) {
            if (childList != null) {
                for (Node eachChild : childList) {
                    if (eachChild.content == c) {
                        return eachChild;
                    }
                }
            }
            return null;
        }
    }

    private Node root;

    public Trie() {
        root = new Node(' ');
    }

    public void insert(String word) {
        if (search(word)) {
            return;
        }

        Node current = root;
        for (int i = 0; i < word.length(); i++) {
            Node child = current.subNode(word.charAt(i));
            if (child != null) {
                current = child;
            } else {
                current.childList.add(new Node(word.charAt(i)));
                current = current.subNode(word.charAt(i));
            }
            current.count++;
        }
        // Set isEnd to indicate end of the word
        current.isEnd = true;
    }

    public boolean search(String word) {
        Node current = root;

        for (int i = 0; i < word.length(); i++) {
            if (current.subNode(word.charAt(i)) == null) {
                return false;
            } else {
                current = current.subNode(word.charAt(i));
            }
        }
        /*
        * This means that a string exists, but make sure its
        * a word by checking its 'isEnd' flag
        */
        return current.isEnd;
    }

    public void deleteWord(String word) {
        if (!search(word)) {
            return;
        }

        Node current = root;
        for (char c : word.toCharArray()) {
            Node child = current.subNode(c);
            if (child.count == 1) {
                current.childList.remove(child);
                return;
            } else {
                child.count--;
                current = child;
            }
        }
        current.isEnd = false;
    }

    public static String getRandomString(int length){
        String str="abcdefghijklmnopqrstuvwxyz/+#";
        Random random=new Random();
        StringBuffer sb=new StringBuffer();
        for(int i=0;i<length;i++){
            int number=random.nextInt(26);
            sb.append(str.charAt(number));
        }
        return sb.toString();
    }

    public static void main(String[] args) {
        Trie trie = new Trie();
        trie.insert("ball");
        trie.insert("balls");
        trie.insert("sense");

        System.out.println(getRandomString(16));
        String searchWord = null;
        for (int i=0; i<1000000;i++) {
            searchWord = getRandomString(16);
            trie.insert(searchWord);
        }

        System.out.println(searchWord);
        long nastart = System.nanoTime();
        for (int i = 0; i < 100; i++) {
            trie.search(searchWord);
        }
        long naend = System.nanoTime();
        System.out.println("== 用时: " + (naend - nastart) / 1000);

        // testing deletion
        System.out.println(trie.search("balls"));
        System.out.println(trie.search("ba"));
        trie.deleteWord("balls");
        System.out.println(trie.search("balls"));
        System.out.println(trie.search("ball"));
    }

}
